The present invention relates generally to automatic-repeat-request (ARQ) transmission protocols in communications systems and, more particularly, to systems and methods for implementing hierarchical acknowledgement bitmaps in ARQ transmission protocols.
In communication systems employing conventional ARQ protocols, such as, for example, sliding window ARQ, a transmitting device can transmit up to N blocks of data (where N equals the send window size) before receiving any acknowledgement (ACK) messages from a receiving device. As is known in the art, a large sliding window advantageously increases channel utilization and data throughput. The receiving device may acknowledge data blocks received from the transmitting device using a conventional flat bitmap. In such a flat bitmap, one bit, called an acknowledge/negative acknowledge (ACK/NACK) bit, is used to acknowledge or negative acknowledge each individual data block in the receive window. The ACK/NACK bit is set to xe2x80x9c1xe2x80x9d if a corresponding block has been received. Otherwise, the ACK/NACK bit is set to xe2x80x9c0xe2x80x9d.
Conventionally, the receiving device includes the flat bitmap in a separate ACK/NACK message and sends the message to the transmitting device on a return channel to acknowledge receipt of the data blocks sent by the transmitting device. The receiving device may also piggyback the bitmap in a header of any data block it sends to the transmitting device. The efficient transmission of acknowledgement bitmaps by the receiving device is an important issue if a large window size is used because the conventional flat bitmap may not fit into a single ACK/NACK message.
The receiving device can divide a long flat bitmap into several partial bitmaps and then send the partial bitmaps using several transmissions. If a partial bitmap is corrupted, however, the transmitting device must wait longer until it can advance its send window since the send window cannot be advanced until the partial bitmap is received. This delay causes the send window to stall and, thus, the transmitting device cannot transmit any new data blocks. Protocol stalling can be a performance limiting factor in an ARQ protocol (e.g., RLC protocol in Enhanced General Packet Radio Service (EGPRS)) with a large window size and having a long round-trip delay.
To overcome the inefficiency of the flat bitmap, the EGPRS protocol, for example, uses a one-dimensional run length coding (based on ITU-T T.4) to compress the bitmap. The T.4 procedure for encoding run lengths, however, can achieve bitmap compression only if, on average, the run lengths are longer than corresponding code words. In many cases, the flat bitmap cannot be compressed, or even worse, the compressed bitmap requires more bits than the flat bitmap.
In accordance with the purpose of the invention as embodied and broadly described herein, a method for communicating data between a transmitting communication device and a receiving communication device includes specifying a number of data blocks in an ARQ receive window; dividing the receive window into a number of sectors, each sector comprising a portion of the number of data blocks in the receive window; receiving, at the receiving communication device, data blocks within the receive window transmitted from the transmitting communication device; constructing an acknowledgement bitmap for each sector in the receive window, the acknowledgement bitmap comprising a sector acknowledgement bit; and transmitting the hierarchical acknowledgement bitmap for each sector to the transmitting communication device.
In another implementation consistent with the present invention, a method for constructing an acknowledgment message in a communication device includes dividing an ARQ receive window into a number of sectors, each sector comprising a portion of a number of data blocks in the receive window; receiving data blocks within the ARQ receive window; and constructing an acknowledgement bitmap for each sector in the receive window, the acknowledgement bitmap comprising a sector acknowledgement bit.
In a further implementation consistent with the present invention, a data structure encoded on a computer readable medium includes acknowledgement data for acknowledging data blocks received in each sector of an ARQ receive window, each sector comprising a portion of a number of data blocks in the receive window, the acknowledgement data comprising a sector acknowledgement bit.
In an additional implementation consistent with the present invention, a method of compressing an acknowledgement bitmap used in an ARQ protocol includes selecting a size for each sector in an ARQ receive window, each sector comprising a portion of a number of data blocks in the receive window; constructing a hierarchical acknowledgement bitmap for each sector in the receive window, the hierarchical acknowledgement bitmap comprising a sector acknowledgement bit; determining a bit compression of a total acknowledgement bitmap comprising the hierarchical bitmaps for each sector in the receive window; and if the bit compression of the total acknowledgement bitmap is not sufficient, re-selecting the size for each sector of the receive window.